package DFS;

import java.util.LinkedList;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution797 {

    List<List<Integer>> allPath = new LinkedList<>();
    List<Integer> path = new LinkedList<>();

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        int dest = graph.length-1;

        traverse(graph,0,dest);

        return allPath;
    }

    public void traverse(int[][] graph,int src,int dest){
        //base case
        if (src < 0 || src >= graph.length){
            return;
        }

        /**
         * 前序操作
         */
        //将src添加入路径
        path.add(src);

        if (src == dest){
            List<Integer> newPath = new LinkedList<>();
            for (Integer integer : path) {
                newPath.add(integer);
            }
            allPath.add(newPath);
        }

        for (int i = 0; i < graph[src].length; i++) {
            traverse(graph,graph[src][i],dest);
        }

        //后序操作
        path.remove(Integer.valueOf(src));
    }

    public static void main(String[] args) {
        int[][] graph = {
                {1, 2},
                {3},
                {3},
                {}
        };

        Solution797 solution797 = new Solution797();
        List<List<Integer>> lists = solution797.allPathsSourceTarget(graph);
        System.out.println("lists = " + lists);
    }
}
